/**
 * Created with Intellij IDEA.
 * Description:
 * User: 28318
 * Date: 2025-10-31
 * Time: 16:26
 */

import java.util.ArrayList;
import java.util.List;

/**
 * 银行家算法核心实现，包括安全检查和资源请求处理
 */
public class BankersAlgorithm {

    // 检查系统是否处于安全状态，返回安全序列或null
    public List<Integer> isSafe(SystemState state) {
        int n = state.getN();
        int m = state.getM();
        int[][] need = state.getNeed();
        int[][] allocation = state.getAllocation();
        int[] available = state.getAvailable();

        // 初始化工作向量和完成标志
        int[] work = available.clone();
        boolean[] finish = new boolean[n];
        List<Integer> safeSequence = new ArrayList<>();

        while (true) {
            boolean found = false;
            // 查找可执行的进程
            for (int i = 0; i < n; i++) {
                if (!finish[i] && isLessOrEqual(need[i], work)) {
                    // 找到可执行进程，加入安全序列
                    safeSequence.add(i);
                    // 释放资源
                    for (int j = 0; j < m; j++) {
                        work[j] += allocation[i][j];
                    }
                    finish[i] = true;
                    found = true;
                    break; // 找到一个后重新开始查找
                }
            }

            if (!found) {
                // 没有找到可执行进程，检查是否所有进程都已完成
                boolean allFinished = true;
                for (boolean f : finish) {
                    if (!f) {
                        allFinished = false;
                        break;
                    }
                }
                if (allFinished) {
                    return safeSequence; // 返回安全序列
                } else {
                    return null; // 不安全状态
                }
            }
        }
    }

    // 处理资源请求
    public boolean requestResource(SystemState state, int processId, int[] request) {
        int n = state.getN();
        int m = state.getM();
        int[][] need = state.getNeed();
        int[] available = state.getAvailable();

        // 检查进程ID是否合法
        if (processId < 0 || processId >= n) {
            System.out.println("错误：进程ID不存在！");
            return false;
        }

        // 检查请求是否合法
        if (!isLessOrEqual(request, need[processId])) {
            System.out.println("请求资源超过最大需求，请求无效！");
            return false;
        }

        if (!isLessOrEqual(request, available)) {
            System.out.println("系统资源不足，请求暂不能满足！");
            return false;
        }

        // 保存当前状态，用于必要时恢复
        int[] oldAvailable = available.clone();
        int[] oldAllocation = state.getAllocation()[processId].clone();
        int[] oldNeed = need[processId].clone();

        // 预分配资源
        for (int j = 0; j < m; j++) {
            available[j] -= request[j];
            state.getAllocation()[processId][j] += request[j];
            need[processId][j] -= request[j];
        }

        // 检查预分配后系统是否安全
        List<Integer> safeSequence = isSafe(state);
        if (safeSequence != null) {
            System.out.println("同意分配！预分配后系统处于安全状态。");
            System.out.println("安全序列为：" + safeSequenceToString(safeSequence));
            return true;
        } else {
            // 不安全，撤销预分配
            System.out.println("分配会导致系统不安全，拒绝请求！");
            state.setAvailable(oldAvailable);
            for (int j = 0; j < m; j++) {
                state.getAllocation()[processId][j] = oldAllocation[j];
                need[processId][j] = oldNeed[j];
            }
            return false;
        }
    }

    // 辅助方法：检查数组a的每个元素是否小于等于数组b的对应元素
    private boolean isLessOrEqual(int[] a, int[] b) {
        for (int i = 0; i < a.length; i++) {
            if (a[i] > b[i]) {
                return false;
            }
        }
        return true;
    }

    // 将安全序列转换为字符串
    public String safeSequenceToString(List<Integer> sequence) {
        if (sequence == null || sequence.isEmpty()) {
            return "";
        }
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < sequence.size(); i++) {
            sb.append("P").append(sequence.get(i));
            if (i < sequence.size() - 1) {
                sb.append(" -> ");
            }
        }
        return sb.toString();
    }
}
